package LeetCode;

import java.util.HashMap;

public class LC_076_MinimumWindowSubstring {
    public static void main(String[] args) {

    }

    static class Solution_1 {
        public String minWindow(String s, String t) {
            HashMap<Character, Integer> needFound = new HashMap<>();
            HashMap<Character, Integer> hasFound = new HashMap<>();
            int min = Integer.MAX_VALUE;
            int minEnd = 0, minStart = 0;
            int end, start;

            char[] chars = t.toCharArray();
            //init hash table
            for (char aChar : chars) {
                if (!needFound.containsKey(aChar))
                    needFound.put(aChar, 0);
                int tmpVal = needFound.get(aChar);
                needFound.replace(aChar, tmpVal + 1);
            }

            chars = s.toCharArray();
            int count = 0;
            int tLength = t.length();

            start = 0;
            for (int i = 0; i < chars.length; i++) {
                char val = chars[i];
                if (needFound.containsKey(val)) {
                    if (!hasFound.containsKey(val))
                        hasFound.put(val, 0);
                    int tmpVal = hasFound.get(val);
                    hasFound.replace(val, ++tmpVal);

                    if (tmpVal <= needFound.get(val))
                        count++;
                }

                if (count == tLength) {
                    end = i;
                    int tmpVal;
                    //向右移动start
                    while (start < end) {
                        if (hasFound.containsKey(chars[start])) {
                            if ((tmpVal = hasFound.get(chars[start])) == needFound.get(chars[start]))
                                break;
                            hasFound.replace(chars[start], --tmpVal);
                        }
                        start++;
                    }
                    if ((end - start + 1) < min) {
                        min = end - start + 1;
                        minEnd = end + 1;
                        minStart = start;
                    }
                    hasFound.replace(chars[start], hasFound.get(chars[start]) - 1);
                    start++;
                    count--;
                }
            }
            if (min == Integer.MAX_VALUE)
                return "";
            return s.substring(minStart, minEnd);
        }
    }

    public class Solution_2 {
        public String minWindow(String s, String t) {
            HashMap<Character, Integer> needFound = new HashMap<>();
            HashMap<Character, Integer> hasFound = new HashMap<>();
            int min = Integer.MAX_VALUE;
            int minEnd = 0, minStart = 0;
            int end, start;

            char[] chars = t.toCharArray();
            for (char aChar : chars) {
                if (!needFound.containsKey(aChar))
                    needFound.put(aChar, 0);
                int tmpVal = needFound.get(aChar);
                needFound.replace(aChar, tmpVal + 1);
            }

            chars = s.toCharArray();
            int count = 0;
            int tLength = t.length();

            start = 0;
            for (int i = 0; i < chars.length; i++) {
                char val = chars[i];
                if (needFound.containsKey(val)) {
                    if (!hasFound.containsKey(val))
                        hasFound.put(val, 0);
                    int tmpVal = hasFound.get(val);
                    hasFound.replace(val, ++tmpVal);

                    if (tmpVal <= needFound.get(val))
                        count++;
                }

                if (count == tLength) {
                    end = i;
                    int tmpVal;
                    //向右移动start
                    while (start < end) {
                        if (hasFound.containsKey(chars[start])) {
                            if ((tmpVal = hasFound.get(chars[start])) == needFound.get(chars[start]))
                                break;
                            hasFound.replace(chars[start], --tmpVal);
                        }
                        start++;
                    }
                    if ((end - start + 1) < min) {
                        min = end - start + 1;
                        minEnd = end + 1;
                        minStart = start;
                    }
                    hasFound.replace(chars[start], hasFound.get(chars[start]) - 1);
                    start++;
                    count--;
                }
            }
            if (min == Integer.MAX_VALUE)
                return "";
            return s.substring(minStart, minEnd);
        }
    }

    public class Solution_3 {
        public String minWindow(String s, String t) {
            HashMap<Character, Integer> dict = new HashMap<>();
            for (int i = 0; i < t.length(); i++) {
                char c = t.charAt(i);
                if (!dict.containsKey(c))
                    dict.put(c, 1);
                else
                    dict.put(c, dict.get(c) + 1);
            }
            HashMap<Character, Integer> found = new HashMap<>();
            int foundCounter = 0;
            int start = 0;
            int end = 0;
            int min = Integer.MAX_VALUE;
            String minWindow = "";
            while (end < s.length()) {
                char c = s.charAt(end);
                if (dict.containsKey(c)) {
                    if (found.containsKey(c)) {
                        if (found.get(c) < dict.get(c))
                            foundCounter++;
                        found.put(c, found.get(c) + 1);
                    } else {
                        found.put(c, 1);
                        foundCounter++;
                    }
                }
                if (foundCounter == t.length()) {
                    char sc = s.charAt(start);
                    while (!found.containsKey(sc) || found.get(sc) > dict.get(sc)) {
                        if (found.containsKey(sc) && found.get(sc) > dict.get(sc))
                            found.put(sc, found.get(sc) - 1);
                        start++;
                        sc = s.charAt(start);
                    }
                    if (end - start + 1 < min) {
                        minWindow = s.substring(start, end + 1);
                        min = end - start + 1;
                    }
                }
                end++;
            }
            return minWindow;
        }
    }
}
